An Achilles' Heel of Term-Resolution

摘要

Term-resolution provides an elegant mechanism to prove that a quantifiedBoolean formula (QBF) is true. It is a dual to Q-resolution (also referred toas clause-resolution) and is practically highly important as it enablescertifying answers of DPLL-based QBF solvers. While term-resolution andQ-resolution are very similar, they're not completely symmetric. In particular,Q-resolution operates on clauses and term-resolution operates on models of thematrix. This paper investigates what impact this asymmetry has. We'll see thatthere is a large class of formulas (formulas with "big models") whoseterm-resolution proofs are exponential. As a possible remedy, the papersuggests to prove true QBFs by refuting their negation ({\em negate-refute}),rather than proving them by term-resolution. The paper shows that from thetheoretical perspective this is indeed a favorable approach. In particular,negation-refutation can p-simulates term-resolution and there is an exponentialseparation between the two calculi. These observations further ourunderstanding of proof systems for QBFs and provide a strong theoreticalunderpinning for the effort towards non-CNF QBF solvers.